package calculate;

/**
 * used Bailey–Borwein–Plouffe formula to generate pi bit by bit
 * v1. accurate to 1000 digits, but not fast enought, do some improvments
 * v2. accurate to 10000 digits, but still too slow
 * v3. accurate to 50000 digits (takes 3 mins), still too slow  
 */
public class BitByBit extends Basic {
	
	long[][] thePowerMod;
	long[] thePower;
	long start = System.nanoTime();
	long mid;
	long end;
	
	public BitByBit(int k) {
		super(k);
		thePowerMod = new long[8][k+100];
		thePower = new long[k+100];
		java.util.Arrays.fill(thePower, -1);
	}

	@Override
	public void calculous() {
		//this.hex.add(3);
		System.out.println("start at: " + this.start);
		for (int i = -1; i < this.preciseDigit; ++i) {
			int temp = getBit(i);
			this.hex[i+1] = temp;
			if (i % 100 == 0) {
				end = start;
				start = System.nanoTime();
				System.out.println("i="+i+" pi:" + temp + "\t[t:"+(start-end)+"(nanoTime)]" );				
			}
		}
		System.out.println("finish at: " + this.start);
	}

	private Integer getBit(int i) {

		double t  = 0;
		t += this.part(1, i) * 4.0;
		t -= this.part(4, i) * 2.0;
		t -= this.part(5, i);
		t -= this.part(6, i);
		while(t<0) t+=1;
		t %= 1.0;

		//System.out.println( "t=" +  t*16 );
		return this.getFirstDigit(t*16);
	}
	
	//calculous the small part as : (b * 16^k) / (8 * k + a)
	//calculous counts from 0 to k
	public double part( int a, int n ) {

		double r = 0;
		double oldR;
		long u = 0; 
		long d = 0;
		int i = 0;
		
		
		if (n % 100 == 0) {
			start = System.nanoTime();
		}
		for (i=0; i<=n; ++i) {
			d = 8 * i + a;
			//r = (r + (1.0*this.power( 16, n - i, d, a, i)) / d) % 1.0;
			r += ((double)this.power( 16, n - i, d, a, i)) / (d);
			//r += (this.power( 16, n - i, d)) / (1.0*d);
			if (r > 100) r %= 1.0;
		}
		
		if (n % 100 == 0) {
			mid = System.nanoTime();
		}
		while(true) {
			oldR = r;
			d = 8 * i + a;
			r = r + 1.0/(this.power(16, i - n) * d);
			if (r - oldR < 0.1) break;
			++i;
		}
		if (n % 100 == 0) {
			end = System.nanoTime();
			//System.out.println("letf: " + (mid - start) + " right: " + (end - mid));
		}
		return r;
	}
	
	//cal b^p
	public long power(int b, int p) {
		if (this.thePower[p] != -1) return this.thePower[p];
		if (p==0) {
			this.thePower[p] = 1;
		}
		else {
			long temp = power(b, p/2 );
			temp = temp * temp;
			if (p%2==1) temp *= b;
			this.thePower[p] = temp;
		}
		return(this.thePower[p]);
		/*
		double out = 1;
		for (long i = 1; i <=p; ++i) {
			out *= b;
		}
		return out;*/
	}

	public long power( long b, long p, long m, int x, int y ) {

		if (p==0) {
			return(this.thePowerMod[x][y] = 1);
		} else {
			return(this.thePowerMod[x][y] = (this.thePowerMod[x][y] * b) % m);
		}
//		System.out.println("x="+x+"y="+y+"p="+p+"out="+this.thePowerMod[x][y]+"other="+this.power(b, p, m));
		

		/*
		long out = 1;
		for (long i = 1; i <= p; ++i) {
			out = (out * b) % m;
		}
		return (out);*/
	}

	public long power( long b, long p, long m) {
	
		if (p==0) return 1;
		long temp = power(b, p/2, m);
		temp = temp * temp;
		if (p%2==1) temp *= b;
		temp %= m;
		return (temp);
	}
}
